{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Adjacent Swaps to Make a Valid Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumSwaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #生成有效数组的最少交换次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个<strong>&nbsp;下标从 0 开始</strong>&nbsp;的整数数组 <code>nums</code>。</p>\n",
    "\n",
    "<p><code>nums</code>&nbsp;上的&nbsp;<strong>相邻&nbsp;</strong>元素可以进行&nbsp;<strong>交换</strong>。</p>\n",
    "\n",
    "<p data-group=\"1-1\">一个&nbsp;<strong>有效&nbsp;</strong>的数组必须满足以下条件:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>最大的元素 (如果有多个，则为最大元素中的任何一个) 位于数组中最右边的位置。</li>\n",
    "\t<li>最小的元素 (如果有多个，则为最小的任何一个元素) 位于数组的最左侧。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<em>使 </em><code>nums</code><em> </em><em>成为有效数组所需的最少交换次数。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [3,4,5,5,3,1]\n",
    "<strong>输出:</strong> 6\n",
    "<strong>解释:</strong> 进行以下交换:\n",
    "- 交换 1:交换第 3 和第 4 个元素，然后 nums 是 [3,4,5,<u><strong>3</strong></u>,<u><strong>5</strong></u>,1].\n",
    "- 交换 2:交换第 4 和第 5 个元素，然后 nums 是 [3,4,5,3,<u><strong>1</strong></u>,<u><strong>5</strong></u>].\n",
    "- 交换 3:交换第 3 和第 4 个元素，然后 nums 是  [3,4,5,<u><strong>1</strong></u>,<u><strong>3</strong></u>,5].\n",
    "- 交换 4:交换第 2 和第 3 个元素，然后 nums 是  [3,4,<u><strong>1</strong></u>,<u><strong>5</strong></u>,3,5].\n",
    "- 交换 5:交换第 1 和第 2 个元素，然后 nums 是  [3,<u><strong>1</strong></u>,<u><strong>4</strong></u>,5,3,5].\n",
    "- 交换 6:交换第 0 和第 1 个元素，然后 nums 是  [<u><strong>1</strong></u>,<u><strong>3</strong></u>,4,5,3,5].\n",
    "可以证明，6 次交换是组成一个有效数组所需的最少交换次数。\n",
    "</pre>\n",
    "<strong class=\"example\">示例 2:</strong>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [9]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong> 该数组已经有效，因此返回 0。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-adjacent-swaps-to-make-a-valid-array](https://leetcode.cn/problems/minimum-adjacent-swaps-to-make-a-valid-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-adjacent-swaps-to-make-a-valid-array](https://leetcode.cn/problems/minimum-adjacent-swaps-to-make-a-valid-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,4,5,5,3,1]', '[9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        min_num, max_num = min(nums), max(nums)\n",
    "        min_index = -1\n",
    "        max_index = -1\n",
    "        for index, num in enumerate(nums):\n",
    "            if num == min_num:\n",
    "                if min_index == -1:\n",
    "                    min_index = index\n",
    "            if num == max_num:\n",
    "                max_index = index\n",
    "        if min_index <= max_index:\n",
    "            return min_index - 0 + n - 1 - max_index\n",
    "        else:\n",
    "            return min_index - 0 + n - max_index - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mn, mx = min(nums), max(nums)\n",
    "        l, r = n-1, 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == mn:\n",
    "                l = min(l, i)\n",
    "            if x == mx:\n",
    "                r = max(r, i)\n",
    "        return l + n - r - 1 - (l > r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        minv,maxv = min(nums),max(nums)\n",
    "        minid,maxid = -1,-1\n",
    "        n = len(nums)\n",
    "        for i in range(n): # 目的是选出最靠左的min，和最靠右的max\n",
    "            if nums[i] == minv:\n",
    "                if minid == -1: \n",
    "                    minid = i\n",
    "            if nums[i] == maxv:\n",
    "                maxid = i\n",
    "        ans = minid - maxid + n - 1\n",
    "        return ans if minid <= maxid else ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        max_num = nums[0]\n",
    "        max_idx = 0\n",
    "\n",
    "\n",
    "        min_num = nums[0]\n",
    "        min_idx = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] >= max_num:\n",
    "                max_num = nums[i]\n",
    "                max_idx = i\n",
    "            if nums[i]<min_num:\n",
    "                min_num = nums[i]\n",
    "                min_idx = i\n",
    "        \n",
    "        if min_idx > max_idx:\n",
    "            return min_idx+len(nums)-1-max_idx -1\n",
    "        else:\n",
    "            return min_idx+len(nums)-1-max_idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        minv, maxv = min(nums), max(nums) # 最大最小值\n",
    "        minid, maxid = -1, -1  # 最大最小值索引\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == minv:\n",
    "                if minid == -1:\n",
    "                    minid = i\n",
    "            if nums[i] == maxv:\n",
    "                maxid = i\n",
    "        ans = minid - maxid + n - 1\n",
    "        return ans if minid <= maxid else ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        M, m = max(nums), min(nums)\n",
    "        i1, i2 = -1, len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == M:\n",
    "                i1 = i\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if nums[i] == m:\n",
    "                i2 = i\n",
    "        ans = len(nums) - 1 - i1 + i2\n",
    "        return ans - 1 if i1 < i2 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        minval, maxval = min(nums), max(nums)\n",
    "        minidx, maxidx = -1, -1\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == minval:\n",
    "                if minidx == -1:\n",
    "                    minidx = i\n",
    "            if nums[i] == maxval:\n",
    "                maxidx = i\n",
    "        res = minidx - maxidx + n - 1\n",
    "        return res if minidx <= maxidx else res - 1\n",
    "\n",
    "#         分别求出最靠近左边的最小值下标以及最靠近右边的最大值下标,计算两个坐标分别到两个端点之间的距离和即可,若最大值坐标在最小值坐标左侧,此时我们会多进行一次计算,返回值减一即可 时间复杂度:O(n)\n",
    "\n",
    "# 作者：Chap\n",
    "# 链接：https://leetcode.cn/problems/minimum-adjacent-swaps-to-make-a-valid-array/solutions/1669002/python3-by-chap_-sw5t/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        length of nums = x\n",
    "        1. iterate the list\n",
    "        2. find m(max index of largest number) and n(min smallest number)\n",
    "        3. if n > m: return n + x - m - 2\n",
    "        else: return n + len(nums) - m - 1\n",
    "        O(n)\n",
    "        '''\n",
    "        n = 0\n",
    "        m = 0\n",
    "\n",
    "        for i in range(0, len(nums)):\n",
    "            if nums[m] <= nums[i]:\n",
    "                m = i\n",
    "            if nums[n] > nums[i]:\n",
    "                n = i\n",
    "        res = n + len(nums) - m - 1\n",
    "        \n",
    "        if n > m:\n",
    "            return res - 1\n",
    "        else:\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        n, imin, imax = len(nums), -1, -1\n",
    "        for i in range(n):\n",
    "            if imax == -1 or nums[i] >= nums[imax]:\n",
    "                imax = i\n",
    "            if imin == -1 or nums[~i] <= nums[imin]:\n",
    "                imin = n-i-1\n",
    "        return imin + n - imax - 1 - (imin > imax) if nums[imax] != nums[imin] else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        minv,maxv = min(nums),max(nums)\n",
    "        minid,maxid = -1,-1\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == minv:\n",
    "                if minid == -1:\n",
    "                    minid = i\n",
    "            if nums[i] == maxv:\n",
    "                maxid = i\n",
    "        ans = minid - maxid + n - 1\n",
    "        return ans if minid <= maxid else ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        minv,maxv = min(nums),max(nums)\n",
    "        minid,maxid = -1,-1\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == minv:\n",
    "                if minid == -1:\n",
    "                    minid = i\n",
    "            if nums[i] == maxv:\n",
    "                maxid = i\n",
    "        ans = minid - maxid + n - 1\n",
    "        return ans if minid <= maxid else ans - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        min_index = 0\n",
    "        min_value = nums[0]\n",
    "        max_index = 0\n",
    "        max_value = nums[0]\n",
    "        for i, v in enumerate(nums):\n",
    "            if v < min_value:\n",
    "                min_value = v\n",
    "                min_index = i\n",
    "            if v >= max_value:\n",
    "                max_value = v\n",
    "                max_index = i\n",
    "        result = len(nums) - 1 - max_index + min_index\n",
    "        if min_index > max_index:\n",
    "            result -= 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        min_left, max_right = min(nums), max(nums)\n",
    "        min_pos = nums.index(min_left)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == max_right:\n",
    "                max_pos = i\n",
    "        ans = min_pos + len(nums) - max_pos - 1\n",
    "        return ans if min_pos <= max_pos else ans - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        n, imin, imax = len(nums), -1, -1\n",
    "        for i in range(n):\n",
    "            if imax == -1 or nums[i] >= nums[imax]:\n",
    "                imax = i\n",
    "            if imin == -1 or nums[~i] <= nums[imin]:\n",
    "                imin = n-i-1\n",
    "        return imin + n - imax - 1 - (imin > imax)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        length of nums = x\n",
    "        1. iterate the list\n",
    "        2. find m(max index of largest number) and n(min smallest number)\n",
    "        3. if n < m: return n + x - m - 2\n",
    "        O(n)\n",
    "        '''\n",
    "        n = 0\n",
    "        m = 0\n",
    "\n",
    "        for i in range(0, len(nums)):\n",
    "            if nums[m] <= nums[i]:\n",
    "                m = i\n",
    "            if nums[n] > nums[i]:\n",
    "                n = i\n",
    "            print(m ,n)\n",
    "        \n",
    "        if n > m:\n",
    "            return n + len(nums) - m - 2\n",
    "        else:\n",
    "            return n + len(nums) - m - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mx_i = nums[::-1].index(max(nums))\n",
    "        print('mx_i=', mx_i)\n",
    "        mn_i = nums.index(min(nums))\n",
    "        print('mn_i=', mn_i)\n",
    "        print(n - mx_i - 1 < mn_i)\n",
    "        return mn_i + mx_i - (n-mx_i-1 < mn_i)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
